package exercises.newcoder.solution;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * <a href="https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=117&&tqId=37778&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking">
 * NC121 字符串的排列</a>
 *
 * @author or2
 * @Description 输入一个字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 * @create 2021年09月04日 时间: 11:06
 */
public class Permutation {
    public ArrayList<String> Permutation(String str) {
//        不可变更 -> 可更改
        StringBuilder inputStr = new StringBuilder(str);
//        存放答案, (去重, 排序)
        TreeSet<String> ans = new TreeSet<>();
//        每次递归所用变量
        StringBuilder curStr = new StringBuilder();
//        正式解答
        recursion(inputStr, ans, curStr);

        return new ArrayList<>(ans);
    }

    private void recursion(StringBuilder inputStr, TreeSet<String> ans, StringBuilder curStr) {
//            如果递归完成, 记录拼接结果
        if (curStr.length() == inputStr.length()) {
            ans.add(curStr.toString());
        }
        for (int j = 0; j < inputStr.length(); j++) {
//                '#' -> 代表被删除
            if (inputStr.charAt(j) == '#') {
                continue;
            }
//                记录当前字符
            char curChar = inputStr.charAt(j);
            curStr.append(curChar);
//                当前字符已使用, 移除当前字符 (用 '#' 标记)
            inputStr.setCharAt(j, '#');
            recursion(inputStr, ans, curStr);
//                递归结束后, 恢复这一字符, 防止影响下一轮循环
            inputStr.setCharAt(j, curChar);
            curStr.deleteCharAt(curStr.length() - 1);
        }
    }
}
